The statistical physics properties of low-density parity-check codes for thebinary symmetric channel are investigated as a spin glass problem withmulti-spin interactions and quenched random fields by the cavity method. Byevaluating the entropy function at the Nishimori temperature, we find thatirregular constructions with heterogeneous degree distribution of check (bit)nodes have higher decoding thresholds compared to regular counterparts withhomogeneous degree distribution. We also show that the instability of themean-field calculation takes place only after the entropy crisis, suggestingthe presence of a frozen glassy phase at low temperatures. When no priorknowledge of channel noise is assumed (searching for the ground state), we findthat a reinforced strategy on normal belief propagation will boost the decodingthreshold to a higher value than the normal belief propagation. This value isclose to the dynamical transition where all local search heuristics fail toidentify the true message (codeword or the ferromagnetic state). After thedynamical transition, the number of metastable states with larger energydensity (than the ferromagnetic state) becomes exponentially numerous. When thenoise level of the transmission channel approaches the static transition point,there starts to exist exponentially numerous codewords sharing the identicalferromagnetic energy.
展开▼
